class Node:
    def __init__(self, value):
        """
            初始化为[ target_list | next ]
        """
        self.value = value
        self.next = None

class Stack:
    def __init__(self):
        self.head = Node("head")    # 初始化添加一个["head"|·]结点
        self.size = 0   # 只有头结点时栈长记0

    def __str__(self):
        """
            栈值Str化输出
            E.X.:Input:[ head | · ]->[ data1 | · ]->[ data2 | None ]
                 Output:"data1->data2"
        """
        cur = self.head.next
        out = ""    # 输出值在空栈时为空
        while cur:
            out += str(cur.value) + "->"
            cur = cur.next
        return out[:-2]  # 输出时去掉最后一个->

    def getSize(self)->int:
        """
            返回栈长
        """
        return self.size

    def isEmpty(self)->bool:
        """
            返回是否空栈的逻辑值
        """
        return self.size == 0

    # Get the top item of the stack
    def peek(self):
        """
            返回栈顶元素值
        """
        if self.isEmpty():
            return None  # 空栈时返回None
        return self.head.next.value

    def push(self, value):
        """
            压栈：将value添加在栈顶
        """
        node = Node(value)
        node.next = self.head.next  # 新节点指向原头结点的后继节点(原栈顶)
        self.head.next = node  # 头结点指向新节点
        self.size += 1  # 栈长+1

    def pop(self):
        """
            出栈：栈顶元素节点删除，返回栈顶元素value
        """
        if self.isEmpty():  # 栈空时抛出异常
            raise Exception("Popping from an empty stack")
        remove = self.head.next
        self.head.next = remove.next    # 头结点指向原栈顶元素的后继
        self.size -= 1
        return remove.value


"""
Q1:
    Tower Of Hanoi
"""
def TowerOfHanoi(n:int, source:str, auxiliary:str, target:str):
    """
    分别有从大到小摆放的盘子 source 和 target
    现在要求将所有的盘子从source柱移动到target柱，每次只能移动一个盘子，并且不能将大的盘子放在小的盘子上。
        算法思路：借助auxiliary进行递归解决。
            首先将前n-1个盘子从A柱借助C柱移动到B柱；
            然后将第n个盘子从A柱移动到C柱；
            最后将前n-1个盘子从B柱借助A柱移动到C柱
    """
    if n > 0:
        TowerOfHanoi(n-1, source, auxiliary, target)  # 将 n-1 个盘子从 source 移动到 auxiliary
        print(" 将盘子 {} 从 {} 移动到 {}".format(n, source, target))  # 将第 n 个盘子从 source 移动到 target
        TowerOfHanoi(n-1, auxiliary, target, source)  # 将 n-1 个盘子从 auxiliary 移动到 target


"""
Q2:
    Given an expression string s, write a program to examine whether the pairs
    and the orders of “{“, “}”, “(“, “)”, “[“, “]” are correct in the given expression.
Example:
    Input: s = “[()]{}{[()()]()}”
    Output: true
        Explanation: All the brackets are well-formed
    Input: s = “[(])”
    Output: false
        Explanation: 1 and 4 brackets are not balanced because there is a closing ‘]’ before the closing ‘(‘
"""
def QuestionTwo(s:str)->bool:
    """
    Given an expression string s, write a program to examine whether the pairs
    and the orders of “{“, “}”, “(“, “)”, “[“, “]” are correct in the given expression.
    When Using This Function, Remenber Stop Print
    """
    stack_temp = Stack()
    for i in range(0,len(s)):
        temp = s[i]
        if stack_temp.isEmpty():
            if temp == "(" or temp == "[" or temp == "{":
            # 空栈时 将上括号入栈 出现下括号判错
                # print("|StackEmpty| Push",temp,"To Empty Stack:")
                stack_temp.push(temp)
                # print("  Now Stack Is Not Empty, Stack:",stack_temp)
            if temp == ")" or temp == "]" or temp == "}":
                return False
        else:
            # if temp == "(" or temp == ")" or temp == "[" or temp =="]" or temp=="{" or temp=="}":
            #     print("|StackNotEmpty|  Judge \"",temp, "\" is Stack's Peek: ", stack_temp)
            # 非空栈时，若temp是某种括号则入栈
            if temp == "(":
                    stack_temp.push(temp)
            elif temp == ")":
                if stack_temp.peek() == "(":
                    stack_temp.pop()
                else:  # print(") Should NOT Match With [ {")
                    return False
            elif temp == "[":
                    stack_temp.push(temp)
            elif temp == "]":
                if stack_temp.peek() == "[":
                    stack_temp.pop()
                else:  # print("] Should NOT Match With ( {")
                    return False
            elif temp == "{":
                    stack_temp.push(temp)
            elif temp == "}":
                if stack_temp.peek() == "{":
                    stack_temp.pop()
                else:  # print("} Should NOT Match With [ (")
                    return False
    if not stack_temp.isEmpty():
        # 对s全字符结束出入栈后 若非空说明有未匹配括号，返回False
        # print("NotEmpty",stack_temp)
        return False
    else:
        return True


"""
Q3:
    Given a string, reverse it using stack. 
Example:
    Input: str = “GeeksQuiz”
    Output: ziuQskeeG
    Input: str = “abc”
    Output: cba
"""
def QuestionThree(s:str)->str:
    stack_temp = Stack()
    result = str()
    for i in range(len(s)):
        stack_temp.push(s[i])
    while not stack_temp.isEmpty():
        result += str(stack_temp.peek())
        stack_temp.pop()
    return result


"""
Q4:
    Given an array target_list[] of size N, the task to reverse the array using Stack.
Examples:
    Input: target_list[] = { 10, 20, 30, 40, 50 } 
        Output: 50 40 30 20 10 
        Explanation: Reversing the array modifies target_list[] to { 50, 40, 30, 20, 10 } 
                    Therefore, the required output is 50 40 30 20 10.
    Input: target_list[] = { 1 } 
        Output: 1
"""
import copy as cy
def QuestionFour(s:Stack):
    if s.isEmpty():
        return None
    node_temp = s.head  # 初始化node_temp指向栈顶
    # 要求不使用getsize方法
    # s为str类时用len返回长度
    size = 1
    while node_temp.next is not None:
        node_temp = node_temp.next
        size += 1
    # 有size为Stack.size
    # node_temp 指向栈尾,再次调用需重置回head
    stack_reverse = Stack()
    temp = size
    while(temp!=1):
        node_temp = s.head
        for i in range(temp):
            node_temp = node_temp.next
            stack_reverse.push(node_temp.value)
            temp -= 1




